package pt.estig.eda;

// Este codigo do algoritmo segui-o o pseudo codigo do pdf da aula
// http://cms.ipbeja.pt/mod/resource/view.php?id=53504
// 

public class quickSort 
{
	/**
	 * @author Fabio Martins 6041 Miguel travassos 6312
	 * @param A
	 * @param p
	 * @param r
	 */
	public  void quicksort(int[] A, int p, int r) {
		if (p < r) {
			int q = partion(A, p, r);
			quicksort(A, p, q - 1);
			quicksort(A, q + 1, r);
		}
	}
	/**
	 * 
	 * @param A
	 * @param p
	 * @param r
	 * @return
	 */
	private  int partion(int[] A, int p, int r) 
	{
		
		int x = A[p];
		int i = p;

		for (int j = p + 1; j <= r; j++) 
		{
			if (A[j] < x) 
			{

				A[i] = A[j];
				A[j] = A[i + 1];
				i = i + 1;
			}
		}
		A[i] = x;
		return i;
	}

}
